package com.meadvc.ssmdemo.util;

import java.util.*;

/**
 * @program: algorithm_test
 * @description: 已知零件集合 list2 种类m,数量n[m]
 * @author: meadvc
 * @create: 2020-06-10 17:48
 **/

public class BacktrackingAlgorithm {

    //最优路径
    static List<Comp> bestList = new ArrayList<Comp>();
    static double total_price = 0;
    //最小价格
    static double best_price = 999999999;

    private static void backtrack(List<List<Comp>> list2, List<Comp> tempList, int index){
        //终结条件
        if(index==list2.size()){
            total_price = 0;
            for(Comp c:tempList){
                total_price+=c.getPrice();
            }
            if(total_price < best_price){
                best_price =total_price;
                bestList.clear();
                bestList.addAll(tempList);
            }
            System.out.println(tempList+"---"+total_price);
        } else{
            //得到缓存列表中的已有的 供应商名称列表
            List<String > tems = new ArrayList<>();
            for(Comp c:tempList){
                tems.add(c.getName());
            }
            //当前处理零件的供应商列表
            List<Comp > li = list2.get(index);
            for(int i=0; i<li.size(); i++) {
                if(tems.contains(li.get(i).getName())) continue;
                //如果缓存供应商名称列表里没有当前供应商名称，就把该供应商加到缓存供应商列表中
                tempList.add(li.get(i));
                backtrack(list2,tempList,index+1);
                //移除缓存供应商列表最后一个供应商
                tempList.remove(tempList.size()-1);
            }
        }

    }

    public static void main(String[] args) {
        System.out.println("测试回溯算法");

        //-----测试数据-----
        //{"零件A","零件B","零件C"};
        //list2 零件ABC的供应商列表分别为li1,,li2,li3,将其添加到list2中
        List<List<Comp>> list2 = new ArrayList<>();
        //Comp(name-名称,price-零件总价（单价*数量）)
        List<Comp> li1 = new ArrayList<>();
        li1.add(new Comp("供应商A",50));
        li1.add(new Comp("供应商B",40));
        li1.add(new Comp("供应商C",30));
        list2.add(li1);
        List<Comp> li2 = new ArrayList<>();
        li2.add(new Comp("供应商A",60));
        li2.add(new Comp("供应商B",30));
        li2.add(new Comp("供应商C",40));
        list2.add(li2);
        List<Comp> li3 = new ArrayList<>();
        li3.add(new Comp("供应商A",30));
        li3.add(new Comp("供应商B",30));
        li3.add(new Comp("供应商C",40));
        list2.add(li3);


        //-----执行算法-----
        backtrack(list2,new ArrayList<>(), 0);

        System.out.println("------------");

        System.out.println(bestList+"---"+best_price);


    }
}
